﻿// 0826train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <deque>

using namespace std;

/*
 题目描述
给定一个 m × n 的矩阵，由若干字符"X"和"O"构成，"X"表示该处已被占据，
"O"表示该处空闲，请找到最大的单入口空闲区域。
解释：
空闲区域是由连通的"O"组成的区域，位于边界的"O"可以构成入口。
单入口空闲区域即只有一个位于边界的"O"作为入口的由连通的"O"组成的区域。
如果两个元素在水平或垂直方向相邻，则称它们是“连通”的。

输入描述：
第一行输入为两个数字，第一个数字为行数m，
第二个数字为列数n，两个数字以空格分隔，1 ≤ m,n ≤ 200，
剩余各行为矩阵各行元素，元素为"X"或"O"，各元素间以空格分隔。

输出描述：
若有唯一符合要求的最大单入口空闲区域，输出三个数字，
第一个数字为入口行坐标（范围为0～行数-1），第二个数字为入口列坐标（范围为0～列数-1），
第三个数字为区域大小，三个数字以空格分隔；
若有多个符合要求的最大单入口空闲区域，输出一个数字，代表区域的大小；
若没有，输出NULL

示例1
输入：
4 4
XXXX
XOOX
XOOX
XOXX
输出：
3 1 5
说明：
存在最大单入口区域，入口行坐标3，列坐标1，区域大小5
 */

class Solution01
{
public:
    void bfsUpdate(
        vector<vector<string>>& grid, 
        vector<vector<bool>>&checked,
        deque<pair<int,int>>&bfs_queue
    )
    {
        while (!bfs_queue.empty())
        {
            pair<int, int>top_node = bfs_queue.front();
            bfs_queue.pop_front();

            //遍历方向矩阵
            for (auto&dir_vec:DirectionGrid)
            {
                //未越界，可到达，未访问
                int curr_r = top_node.first + dir_vec[0];
                int curr_c = top_node.second + dir_vec[1];

                bool is_curr_r = curr_r >= 0 && curr_r < row_size;
                bool is_curr_c = curr_c >= 0 && curr_c < col_size;

                if (is_curr_r&&is_curr_c)
                {
                    bool is_available = grid[curr_r][curr_c] == "O";
                    bool is_visited = checked[curr_r][curr_c];

                    if (is_available && !is_visited)
                    {
                        if (checkIn(grid, curr_r,curr_c))
                        {
	                        //边界有入口，区域并非单入口
                            curr_verify = false;
                        }

                        curr_count += 1;
                        bfs_queue.push_back(make_pair(curr_r, curr_c));
                        //标记已访问
                        checked[curr_r][curr_c] = true;
                    }
                }


            }

        }
	    //bfsUpdate
    }

    bool checkIn(vector<vector<string>>&grid, int row, int  col)
    {
        if (grid[row][col]=="O")
        {
            //第一行或者最后一行
            if (row == 0 || row == row_size - 1) return true;
            //第一列，或者最后一列
            if (col == 0 || col == col_size - 1) return true;
        }

        return false;
    }

    Solution01(vector<vector<string>>&grid)
    {
        row_size = grid.size();
        col_size = grid[0].size();
        //假设只有1个
		//双重循环
        //checked bfs_queue DirectionGrid
        vector<bool>checked_status(col_size, false);
        vector<vector<bool>>checked(row_size, checked_status);

        deque<pair<int, int>>bfs_queue;
        //双重循环
        for (int r=0; r<row_size; r++)
        {
            for (int c=0; c<col_size; c++)
            {
                //未访问 可到达 入队列
                bool first_visited = checked[r][c];
                bool first_available = checkIn(grid, r, c);

                if (first_available && !first_visited)
                {
                    curr_count = 1;
                    bfs_queue.push_back(make_pair(r, c));
                    //标记已访问
                    checked[r][c] = true;

                    curr_verify = true; //区域是否单入口
                    bfsUpdate(grid, checked, bfs_queue);

                    if (curr_verify)
                    {
                        if (curr_count > max_count)
                        {
                            max_count = curr_count;
                            pos_vec.clear();
                            pos_vec.push_back(make_pair(r, c));
                        }
                        else if (curr_count == max_count)
                        {
                            pos_vec.push_back(make_pair(r, c));
                        }
                    }
                    //bfsUpdate
                }

                //for col_size
            }
            //for row_size
        }

        if (max_count==0)
        {
            //若没有，输出NULL
            cout << "NULL";
            return;
        }

        if (pos_vec.size()>1)
        {
            cout << max_count;
            return;
        }
        else if (pos_vec.size() == 1)
        {
            cout << pos_vec[0].first << ' ';
            cout << pos_vec[0].second << ' ';
            cout << max_count;
        }

        //Solution01
    }
private:
    bool curr_verify = true; //区域是否单入口
    vector<vector<int>>DirectionGrid = {{-1,0},{1,0},{0,-1},{0,1}};
    int row_size = 0, col_size = 0;
    int max_count = 0, curr_count = 0;
    vector<pair<int, int>>pos_vec;
};



int main()
{
/*
XXXX
XOOX
XOOX
XOXX

XXXXX
OOOOX
XOOOX
XOXXO

XXXX
XOOO
XOOO
XOOX
XXXX
*/
    string str1 = "XXXX", str2 = "XOOO", str3 = "XOOO", str4 = "XOOX", str5 = "XXXX";
    vector<string>str_vec = { str1, str2, str3, str4,str5 };
    vector<vector<string>>grid;

    for (auto&oh_str:str_vec)
    {
        vector<string>min_vec;
        for (auto&oh_char:oh_str)
        {
            string curr;
            curr += oh_char;
            min_vec.push_back(curr);
        }
        grid.push_back(min_vec);
    }
    Solution01 solu(grid);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
